# This is the performance evaluation code for PSP
# Author: Zongjian He
# Date:  Revision 1. 2013.7.23
import time
import math
import random
import csv
from operator import itemgetter
from collections import OrderedDict
from Tkinter import *



class Cfg:
    gR = list()  # region vector
    gC = list()  # cost vector
    gP = list()  # global input matrix
    k = 30
#end class

def GenDMatrix():
    Cfg.gR = []
    Cfg.gC = []
    Cfg.gP=[
            ['A1', 'B2', 'A2', 'A1'],
            ['A2', 'B1', 'B2', 'A1'],
            ['A2', 'B1', 'B2', 'A1'],
            ['A2', 'B1', 'B2', 'A1']
#       ['A', 'B', 'C', 'D', 'D'],
#       ['B', 'A', 'B', 'D', 'B'],
#       ['B', 'C', 'D', 'D', 'A'],
#       ['C', 'D', 'D', 'A', 'B'],
#       ['D', 'D', 'A', 'B', 'C'],
#       ['D', 'D', 'D', 'D', 'D'],
#       ['A', 'A', 'A', 'A', 'A'],
       ]
    Cfg.gR.extend(['A1','B2','B1','A2'])
    Cfg.gC.extend([1,1,1,1,1,1,1])
    #gC.extend([2,3,3])
#end def

# Generate matrix with vehicle number vn, time slot tn, region number rn
def GenMatrix(vn, tn, rn = 5):
    Cfg.gR = []
    Cfg.gC = []
    # generate region
    for i in range(rn): 
        for j in range(rn):
            Cfg.gR.append("%c%d" %(chr(65 + i), j+1))
    # generate vn vehicle
    Cfg.gP = list()
    for i in range(vn):
        vi = list()
        for j in range(tn):
            vi.append(random.choice(Cfg.gR))
        # end for
        Cfg.gP.append(vi)
        # generate cost vector
        #Cfg.gC.append(random.randint(1,4))
        Cfg.gC.append(1)
    # end for
    return Cfg.gP
#end GenMatrix

def DumpMatrix():
    l = 1;
    for i in Cfg.gP:
        print "%d (%d): %r" % (l, Cfg.gC[l-1], i)
        l += 1 
#end DumpMatrix

def GetTSC(S):
    tsc = 0
    if len(S) == 0: return tsc
    for i in range(len(S[0])):
        s = set()
        for j in range(len(S)): s.add(S[j][i])
        tsc += len(s)
    #end for
    return tsc
#end GetTSC

def GetMTC(S):
    if len(S) == 0: return 0
    # end if
    mtc = len(S)
    rmap = dict()
    for r in Cfg.gR: rmap[r] = 0
    #end for
    for i in range(len(S[0])):
        s = set()
        for j in range(len(S)): s.add(S[j][i])
        #end for
        for t in s: rmap[t] += 1
    #end for
    for rv in rmap.values():
        if rv < mtc: mtc = rv
    # end for
    return mtc
#end GetMTC


def GreedyTSC(k):
    lP = list(Cfg.gP)
    curk = 0
    S = []
    while curk < k:
        maxce = -1
        maxi = -1
        # calculate ce
        for i in range(len(lP)):
            if curk + Cfg.gC[i] > k: continue
            Temp = list(S)
            Temp.append(lP[i])
            deltaTSC = GetTSC(Temp) - GetTSC(S)
            ce = float(deltaTSC) / Cfg.gC[i]
            if ce > maxce:
                maxce = ce
                maxi = i
            #end if
        #end for
        if maxi == -1: break
        S.append(lP[maxi])
        curk += Cfg.gC[i]
        del lP[maxi]
    #end while
    print S
    return S
#end GreedyTSC

def RandomSolution():
    rs = []
    curk = 0
    while curk < Cfg.k:
        i = random.randint(0, len(Cfg.gP)-1)
        if curk + Cfg.gC[i] >= Cfg.k: break
        rs.append(Cfg.gP[i])
        curk += Cfg.gC[i]
    # end while
    return rs

class GA:
    mutation_prob = 0.025
    elite_prob = 0.1
    max_iteration = 10
    population_size = 100
    
    def GetCost(self, sl):
        tk = 0
        for i in range(len(sl)):
            if sl[i] == 1 : tk += Cfg.gC[i]
        return tk
    
    def FixSolution(self, sl, k):
        # check the capacity
        tk = self.GetCost(sl)
        if tk <=k: return sl
        #begin to fix
        civ = [(Cfg.gC[i], i) for i in range(len(Cfg.gC))]
        civ.sort(reverse=True)
        for (c,i) in civ:
            sl[i] = 0
            if self.GetCost(sl) <= k : return sl
        #end for
        print self.GetCost(sl)
        return sl

    def InitPopulation(self):
        self.mPopulation = list()
        for i in range(GA.population_size):
            sl = []
            for j in range(len(Cfg.gP)):
                sl.append( random.choice([0, 1]) )
            sl = self.FixSolution(sl, Cfg.k)
            self.mPopulation.append(sl)
        #end for
        
    def StrToSln(self, str):
        S = []
        for i in range(len(str)):
            if str[i] == 1: S.append(Cfg.gP[i])
        return S
    
    def FitnessFn(self, individual):
        S = self.StrToSln(individual)
        fitness = GetMTC(S)
        return fitness
        
    def CrossoverFn(self, p1, p2):
        ipos = random.randint(1, len(p1)-2)
        return self.FixSolution(p1[0:ipos] + p2[ipos:], Cfg.k)
    
    def MutationFn(self, p):
        ipos = random.randint(0, len(p)-1)
        if p[ipos] == 1:
            p[ipos] = 0
        else:
            p[ipos] = 1
        #end if
        return self.FixSolution(p, Cfg.k)
    
    def Run(self):
        self.InitPopulation()
        
        top_elite = int(GA.elite_prob * GA.population_size)
        
        for i in range(GA.max_iteration):
            individual_scores = [(self.FitnessFn(v), v) for v in self.mPopulation]
            individual_scores.sort(reverse=True)
            
            ranked_individual = [v for (s, v) in individual_scores]
            
            # population winner
            self.mPopulation = ranked_individual[0:top_elite]
            
            # add mutated and bred forms of the winner
            while len(self.mPopulation) < GA.population_size:
                if random.random() < GA.mutation_prob:
                    # mutation
                    c = random.randint(0, top_elite)
                    self.mPopulation.append(self.MutationFn(ranked_individual[c]))
                else:
                    # crossover
                    c1 = random.randint(0, top_elite)
                    c2 = random.randint(0, top_elite)
                    self.mPopulation.append(self.CrossoverFn(ranked_individual[c1], ranked_individual[c2]))
                #end if
            #end while
            
            # stop before
            #if individual_scores[0][0] == len(Cfg.gP[0]):
            #    print self.GetCost(individual_scores[0][1])
            #    return self.StrToSln(individual_scores[0][1])
        #end for
        print self.GetCost(individual_scores[0][1])
        return self.StrToSln(individual_scores[0][1])
#end class


def DrawP():
    
    # generate density dict
    dd = dict()
    for k in Cfg.gR: dd[k] = 0
    for v in Cfg.gP:
        for t in v: dd[t] += 1
    #end for
    master = Tk()
    w = Canvas(master, width=800, height=600)
    w.pack()
    
    WIDTH = 50
    # draw density map
    for d in dd.keys():
        x = ord(d[0]) - 64
        y = int(d[1:])
        c = "#"
        for i in range(6): c += "%x" % (0xf-dd[d])
        w.create_rectangle(x*WIDTH, y*WIDTH, (x+1)*WIDTH, (y+1)*WIDTH, fill=c)
    # draw index
    for i in range(1, 20): w.create_text(20+i*50, 30, text=str(i))
    for i in range(1, 20): w.create_text(30, 20+i*50, text=str(chr(64+i)))
              
    mainloop()

# vehicle number, region number, time number
def EvalTimeComplexityVN():
    # vehicle number
    vnp = []
    for i in range(1,11):
        vn = 100 * i
        GenMatrix(vn, 10, 10)
        # calculate GR and GN
        t1 = time.time()
        S = GreedyTSC(Cfg.k)
        t2 = time.time()
        ga = GA()
        t3 = time.time()
        S = ga.Run()
        t4 = time.time()
        vnp.append([vn, t2-t1, t4-t3])
    #end for

    with open('./vnp.txt', 'a') as f:
        for v in vnp:
            opt = "%d, %f, %f \r\n" % (v[0], v[1], v[2])
            print opt,
            f.write(opt)
    #end with
    
def EvalTimeComplexityRN():
    # region number
    rnp = []
    for i in range(1,11):
        rn = 10 * i
        GenMatrix(100, 10, rn)
        # calculate GR and GN
        t1 = time.time()
        S = GreedyTSC(Cfg.k)
        t2 = time.time()
        ga = GA()
        t3 = time.time()
        S = ga.Run()
        t4 = time.time()
        rnp.append([rn*rn, t2-t1, t4-t3])
    #end for

    with open('./rnp.txt', 'a') as f:
        for v in rnp:
            opt = "%d, %f, %f \r\n" % (v[0], v[1], v[2])
            print opt,
            f.write(opt)
    #end with

def EvalTimeComplexityTN():
    # time number
    tnp = []
    for i in range(1,11):
        tn = 5 * i
        GenMatrix(100, tn, 10)
        # calculate GR and GN
        t1 = time.time()
        S = GreedyTSC(Cfg.k)
        t2 = time.time()
        ga = GA()
        t3 = time.time()
        S = ga.Run()
        t4 = time.time()
        tnp.append([tn, t2-t1, t4-t3])
    #end for

    with open('./tnp.txt', 'a') as f:
        for v in tnp:
            opt = "%d, %f, %f \r\n" % (v[0], v[1], v[2])
            print opt,
            f.write(opt)
    #end with
    
def EvalTimeComplexityGA():
    # time number
    gap = []
    GenMatrix(100, 10, 5)
    for i in range(1,11):
        iter = i * 10
        pop = i * 100
        # calculate GR and GN
        t1 = time.time()
        ga = GA()
        GA.max_iteration = iter
        GA.population_size = 100
        S = ga.Run()
        t2 = time.time()
        
        t3 = time.time()
        ga = GA()
        GA.max_iteration = 10
        GA.population_size = pop
        S = ga.Run()
        t4 = time.time()
        
        gap.append([i, t2-t1, t4-t3])
    #end for

    with open('./gap.txt', 'a') as f:
        for v in gap:
            opt = "%d, %f, %f \r\n" % (v[0], v[1], v[2])
            print opt,
            f.write(opt)
    #end with


def EvalAccuracyGreedyK():
    # vehicle number
    grp = []
    GenMatrix(100, 10, 5)
    for i in range(1, 35, 3):
        Cfg.k = i
        S = GreedyTSC(Cfg.k)
        gtsc = GetTSC(S)
        S = RandomSolution()
        rtsc = GetTSC(S)
        
        grp.append([Cfg.k, gtsc, rtsc, Cfg.k * len(Cfg.gP[0])])
    #end for
    with open('./a_gr_k.txt', 'a') as f:
        for v in grp:
            opt = "%d, %d, %d, %d\r\n" % (v[0], v[1], v[2], v[3])
            print opt,
            f.write(opt)
    #end with
    
    
def EvalAccuracyGreedyT():
    # vehicle number
    grt = []
    for i in range(2, 30, 2):
        GenMatrix(1000, i, 8)
        S = GreedyTSC(Cfg.k)
        gtsc = GetTSC(S)
        S = RandomSolution()
        rtsc = GetTSC(S)
        grt.append([i, gtsc, rtsc, Cfg.k * len(Cfg.gP[0])])
    #end for
    with open('./a_gr_t.txt', 'a') as f:
        for v in grt:
            opt = "%d, %d, %d, %d\r\n" % (v[0], v[1], v[2], v[3])
            print opt,
            f.write(opt)
    #end with
    
def EvalAccuracyGreedyV():
    # vehicle number
    grv = []
    for i in range(2, 20):
        vn = i * 100
        GenMatrix(vn, 80, 5)
        S = GreedyTSC(Cfg.k)
        gtsc = GetTSC(S)
        S = RandomSolution()
        rtsc = GetTSC(S)
        grv.append([vn, gtsc, rtsc, Cfg.k * len(Cfg.gP[0])])
    #end for
    with open('./a_gr_v.txt', 'a') as f:
        for v in grv:
            opt = "%d, %d, %d, %d\r\n" % (v[0], v[1], v[2], v[3])
            print opt,
            f.write(opt)
    #end with

def EvalAccuracyGaI():
    gaa = []
    GenMatrix(1000, 20, 5)
    for i in range(1,11):
        niter = i * 10
        # calculate GR and GN
        ga = GA()
        GA.max_iteration = niter
        GA.population_size = 100
        S = ga.Run()
        gmtc = GetMTC(S)
        S = RandomSolution()
        rmtc = GetMTC(S)
        gaa.append([niter, gmtc, rmtc, len(Cfg.gP[0])])

    with open('./a_ga_i.txt', 'a') as f:
        for v in gaa:
            opt = "%d, %d, %d, %d\r\n" % (v[0], v[1], v[2], v[3])
            print opt,
            f.write(opt)
    #end with
    
def EvalAccuracyGaP():
    gaa = []
    GenMatrix(1000, 20, 5)
    for i in range(1,11):
        print i
        pop = i * 50
        # calculate GR and GN
        ga = GA()
        GA.max_iteration = 10
        GA.population_size = pop
        S = ga.Run()
        gmtc = GetMTC(S)
        S = RandomSolution()
        rmtc = GetMTC(S)
        gaa.append([pop, gmtc, rmtc, len(Cfg.gP[0])])

    with open('./a_ga_p.txt', 'a') as f:
        for v in gaa:
            opt = "%d, %d, %d, %d\r\n" % (v[0], v[1], v[2], v[3])
            print opt,
            f.write(opt)
    #end with
    
def demo():
    #EvalTimeComplexityVN()
    #EvalTimeComplexityRN()
    #EvalTimeComplexityTN()
    #EvalTimeComplexityGA()
    #EvalAccuracyGreedyK()
    #EvalAccuracyGreedyT()
    #EvalAccuracyGreedyV()
    #EvalAccuracyGaI()
    EvalAccuracyGaP()
    #EvalApplication()

if __name__ == '__main__':
    random.seed(1234)
    T = time.time()
    demo()
    t1 = time.time() - T
    print "%s seconds" % (t1)
    